#include <stdio.h>
#include <stdlib.h>

// 三叉树结点结构
typedef struct TernaryNode
{
    int data;
    struct TernaryNode *left;
    struct TernaryNode *middle;
    struct TernaryNode *right;
} TernaryNode;

// 二叉树结点结构
typedef struct BinaryNode
{
    int data;
    struct BinaryNode *left;
    struct BinaryNode *right;
} BinaryNode;

// 创建三叉树结点
TernaryNode *createTernaryNode(int data)
{
    TernaryNode *newNode = (TernaryNode *)malloc(sizeof(TernaryNode));
    newNode->data = data;
    newNode->left = NULL;
    newNode->middle = NULL;
    newNode->right = NULL;
    return newNode;
}

// 将三叉树转换为二叉树
BinaryNode *convertTernaryToBinary(TernaryNode *root)
{
    if (root == NULL)
    {
        return NULL;
    }

    // 创建对应的二叉树结点
    BinaryNode *binaryNode = (BinaryNode *)malloc(sizeof(BinaryNode));
    binaryNode->data = root->data;
    binaryNode->left = NULL;
    binaryNode->right = NULL;

    // 转换左子树
    if (root->left != NULL)
    {
        binaryNode->left = convertTernaryToBinary(root->left);
    }

    // 转换中间和右子树
    if (root->middle != NULL || root->right != NULL)
    {
        BinaryNode *temp = binaryNode;

        // 处理中间子树
        if (root->middle != NULL)
        {
            temp->right = convertTernaryToBinary(root->middle);
            temp = temp->right;
        }

        // 处理右子树
        if (root->right != NULL)
        {
            temp->right = convertTernaryToBinary(root->right);
        }
    }

    return binaryNode;
}

// 打印二叉树（中序遍历）
void printBinaryTree(BinaryNode *root)
{
    if (root != NULL)
    {
        printBinaryTree(root->left);
        printf("%d ", root->data); // 打印结点数据
        printBinaryTree(root->right);
    }
}

// 打印三叉树（前序遍历）
void printTernaryTree(TernaryNode *root)
{
    if (root != NULL)
    {
        printf("%d ", root->data); // 打印结点数据
        printTernaryTree(root->left);
        printTernaryTree(root->middle);
        printTernaryTree(root->right);
    }
}

int main()
{
    // 创建示例三叉树
    TernaryNode *root = createTernaryNode(1);
    root->left = createTernaryNode(2);
    root->middle = createTernaryNode(3);
    root->right = createTernaryNode(4);
    root->left->left = createTernaryNode(5);
    root->left->middle = createTernaryNode(6);
    root->left->right = createTernaryNode(7);

    printf("Original ternary tree (preorder): "); // 原始三叉树（前序遍历）
    printTernaryTree(root);
    printf("\n");

    // 转换为二叉树
    BinaryNode *binaryRoot = convertTernaryToBinary(root);

    printf("Converted binary tree (inorder): "); // 转换后的二叉树（中序遍历）
    printBinaryTree(binaryRoot);
    printf("\n");

    return 0;
}